import sys
import math

def  bitLen(int_type):
    length = 0
    while (int_type):
        int_type>>=1
        length += 1
    return length


# Iterative Algorithm (xgcd)
def iterative_egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q,r = b/a,b%a; m,n = x-u*q,y-v*q # use x//y for floor "floor division"
        b,a, x,y, u,v = a,r, u,v, m,n
    return b, x, y
 
# Recursive Algorithm
def recursive_egcd(a, b):
    """Returns a triple (g, x, y), such that ax + by = g = gcd(a,b).
       Assumes a, b >= 0, and that at least one of them is > 0.
       Bounds on output values: |x|, |y| <= max(a, b)."""
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = iterative_egcd(a, m)  # or recursive_egcd(a, m)
    if g != 1:
        return None
    else:
        return x % m


def verify_dsa_params  (p, q, g) :
    p1=p-1
    p2=p1/q
    #print(" p2=(p-1)/q = %x\n" %  p2)
    p3 = (p2*q)+1
    #print("p3 = p2*q +1 = %x\n" %  p3)
    #print("p3-q = %x\n" % (p3-p))
    if p3 - p == 0 :
        print "dsa param check ok"
    else:
        print "dsa param check FAILED"    
    # test bit lengths
    p_bl = bitLen(p)
    q_bl = bitLen(q)
    g_bl = bitLen(g)
    print  "bit length p = ",p_bl," q = ",q_bl," g = ", g_bl

def test_modiv (S,W,q):
    res = W * S
    res = res % q
    
    if res != 1 :
        print "!!!! Modular inverse failed "
    



#------------------------------------------------------------
# DSA parameters are gerates with openssl: 
# openssl dsaparam -text 128 -out <file>

p = 0x00e9b980ab443ad4ece1a18e369e77e4cd56daf5f3787652710e98985972c2544e920c648c28265ce0c67e24a2714509ac8fb20261fa13767fb053f11f62e9bfa3
q = 0x00bd57a7e5ff26b784e76856298c7f67de370db51d
g = 0x1c72541c32713859203d1396e4068ce242b1d6245f1efcf3cc76b99e7a65475dd298533df3a277ddf6dd725f0b02fda4fe41d475708959925ca588ac93be617a


print "--------------- dsa parameters  ------------------"
verify_dsa_params (p, q, g)

print("p = %x\n" % p)
print("q = %x \n" % q)
print("g = %x\n" %g)

#------------------------------------------------------------
# X private key, generate X in the range [1, q-1]
X=12363749

# Y public key   Y= g^x mod p
Y = pow(g,X,p)
print "Y= ",Y,"\n"

# K a secret number unique to each message, randomly generated.
K = 162733838383837377737373

#------------------------------------------------------------
### compute DSA Parameters.
# r = (g^k mod p) mod q
# s = (k^-1 (z + x.r)) mod q
print "--------------- signature generation ------------------"

# Compute a signature.
hash=0x49bcccedf477dfb3a62bea90fc54ac34ebe0903f
print "hash bitlen = ",bitLen(hash)
print "hash =", "%x" % hash

t1=pow(g,K,p) 
R=t1 % q
print "r=",R

# compute le modular inverse of K mod q
Kinv = modinv(K,q)

test_modiv (K, Kinv, q)

S = (Kinv * ( hash + (X * R))) % q
 
print "s=",S

#------------------------------------------------------------
print "--------------- signature verification ------------------"
print "signature is  composed of s, q, z, r, p, y"
print "the message hash is z"
Z = hash

W = modinv(S,q)

test_modiv (W,S,q)

u1 =  (Z * W) % q
u2 =  (R * W) % q
#v = (((g ** u1) * (y ** u2)) % p ) % q
f1 = pow(g,u1, p)
f2 = pow(Y,u2, p)
v = ((f1 * f2 ) %p ) %q

print "v=",v
print "r=",R

if v  ==  R :
    print "Signature match"
else:
    print "Wrong Signature"

